package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yyq
 * @create 2022-04-28 9:48
 */
public class leetcode131 {
    public List<List<String>> partition(String s) {
        List<List<String>> lists =new ArrayList<>();
        List<String> path = new ArrayList<>();
        int startIndex = 0;
        backTracking(lists,path,startIndex,s);
        return lists;
    }

    private void backTracking(List<List<String>> lists, List<String> path, int startIndex,String s) {
        if(startIndex==s.length()){
            lists.add(new ArrayList<>(path));
            return;
        }
        // 是截取startIndex - i 的字符串 判断该字符串是否为回文字符串
        for (int i = startIndex; i < s.length();i++){
            if(isHUIWen(s,startIndex,i)){
                path.add(s.substring(startIndex,i+1));
            }
            else {
                continue;
            }
            backTracking(lists,path,i+1,s);
            path.remove(path.size()-1);
        }
    }
    public boolean isHUIWen(String s,int begin,int end){
        while (begin<end){
            if(s.charAt(begin)!=s.charAt(end)){
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }
}
